<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>算法解析：两个数组的交集 II</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            color: #333;
            line-height: 1.6;
            background-color: #f9fafb;
        }
        .hero {
            background: linear-gradient(135deg, #6b46c1 0%, #4c51bf 100%);
        }
        .hero-title {
            text-shadow: 0 2px 4px rgba(0,0,0,0.2);
        }
        .code-block {
            background-color: #2d3748;
            border-radius: 0.5rem;
            box-shadow: 0 4px 6px -1px rgba(0, 0, 0, 0.1), 0 2px 4px -1px rgba(0, 0, 0, 0.06);
        }
        .card {
            transition: all 0.3s ease;
            box-shadow: 0 1px 3px rgba(0,0,0,0.1);
        }
        .card:hover {
            transform: translateY(-5px);
            box-shadow: 0 10px 25px rgba(0,0,0,0.1);
        }
        .highlight {
            position: relative;
        }
        .highlight:after {
            content: '';
            position: absolute;
            bottom: 0;
            left: 0;
            width: 100%;
            height: 30%;
            background-color: rgba(167, 139, 250, 0.3);
            z-index: -1;
            transition: all 0.3s ease;
        }
        .highlight:hover:after {
            height: 45%;
        }
        .solution-card {
            border-left: 4px solid #6b46c1;
        }
        .list-item {
            position: relative;
            padding-left: 1.5rem;
        }
        .list-item:before {
            content: '•';
            position: absolute;
            left: 0;
            color: #6b46c1;
            font-weight: bold;
        }
    </style>
</head>
<body class="antialiased">
    <!-- Hero Section -->
    <section class="hero text-white py-20 px-4 md:px-0">
        <div class="container mx-auto max-w-4xl flex flex-col items-center text-center">
            <h1 class="hero-title text-4xl md:text-5xl font-bold mb-6">两个数组的交集 II</h1>
            <p class="text-xl md:text-2xl opacity-90 mb-8 max-w-2xl">探索高效算法，找出数组间的完美匹配</p>
            <div class="flex space-x-4">
                <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">哈希表</span>
                <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">双指针</span>
                <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full text-sm font-medium">算法优化</span>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="container mx-auto max-w-4xl px-4 py-12">
        <!-- Problem Statement -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <i class="fas fa-question-circle text-2xl text-purple-600 mr-3"></i>
                <h2 class="text-3xl font-bold text-gray-800">题目描述</h2>
            </div>
            <div class="bg-white rounded-xl p-6 shadow-md">
                <p class="text-lg text-gray-700 leading-relaxed">
                    给定两个数组，编写一个函数来计算它们的交集。输出结果中每个元素出现的次数应与它在两个数组中出现次数的最小值一致。
                </p>
                <div class="mt-4 p-4 bg-gray-50 rounded-lg border border-gray-200">
                    <p class="font-medium text-gray-800">示例:</p>
                    <p class="text-gray-700">输入: nums1 = [1, 2, 2, 1], nums2 = [2, 2]</p>
                    <p class="text-gray-700">输出: [2, 2]</p>
                    <p class="text-gray-600 mt-2 text-sm">解释: 数字2在两个数组中都出现了两次，因此结果中包含两个2</p>
                </div>
            </div>
        </section>

        <!-- Core Concepts -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <i class="fas fa-lightbulb text-2xl text-yellow-500 mr-3"></i>
                <h2 class="text-3xl font-bold text-gray-800">核心考点与算法</h2>
            </div>
            <div class="grid md:grid-cols-2 gap-6">
                <!-- Hash Table Card -->
                <div class="card bg-white rounded-xl p-6 solution-card">
                    <div class="flex items-center mb-4">
                        <div class="w-10 h-10 rounded-full bg-purple-100 flex items-center justify-center mr-3">
                            <i class="fas fa-hashtag text-purple-600"></i>
                        </div>
                        <h3 class="text-xl font-bold text-gray-800">哈希表方法</h3>
                    </div>
                    <p class="text-gray-700 mb-4">
                        统计第一个数组中各元素的频率，然后遍历第二个数组，检查元素是否存在于哈希表中并减少频率。
                    </p>
                    <div class="text-sm text-gray-500">
                        <p class="list-item mb-1">时间复杂度: O(n + m)</p>
                        <p class="list-item">空间复杂度: O(min(n, m))</p>
                    </div>
                </div>

                <!-- Two Pointers Card -->
                <div class="card bg-white rounded-xl p-6 solution-card">
                    <div class="flex items-center mb-4">
                        <div class="w-10 h-10 rounded-full bg-blue-100 flex items-center justify-center mr-3">
                            <i class="fas fa-arrows-alt-h text-blue-600"></i>
                        </div>
                        <h3 class="text-xl font-bold text-gray-800">双指针方法</h3>
                    </div>
                    <p class="text-gray-700 mb-4">
                        对两个数组排序后，使用双指针遍历，比较元素并记录交集。
                    </p>
                    <div class="text-sm text-gray-500">
                        <p class="list-item mb-1">时间复杂度: O(n log n + m log m)</p>
                        <p class="list-item">空间复杂度: O(1) (不计输出空间)</p>
                    </div>
                </div>
            </div>
        </section>

        <!-- Visualization -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <i class="fas fa-project-diagram text-2xl text-green-500 mr-3"></i>
                <h2 class="text-3xl font-bold text-gray-800">算法图解</h2>
            </div>
            <div class="bg-white rounded-xl p-6 shadow-md">
                <div class="mermaid">
                    graph TD
                    A[开始] --> B{数组是否已排序?}
                    B -->|是| C[使用双指针方法]
                    B -->|否| D[使用哈希表方法]
                    C --> E[排序两个数组]
                    E --> F[初始化双指针i,j=0]
                    F --> G{比较nums1[i]和nums2[j]}
                    G -->|相等| H[添加到结果, i++, j++]
                    G -->|nums1[i] < nums2[j]| I[i++]
                    G -->|nums1[i] > nums2[j]| J[j++]
                    H --> K{指针是否越界?}
                    I --> K
                    J --> K
                    K -->|否| G
                    K -->|是| L[结束]
                    D --> M[统计nums1元素频率]
                    M --> N[遍历nums2检查频率]
                    N --> O[频率>0则添加结果]
                    O --> P[减少频率]
                    P --> Q[结束]
                </div>
            </div>
        </section>

        <!-- Code Implementation -->
        <section class="mb-16">
            <div class="flex items-center mb-6">
                <i class="fas fa-code text-2xl text-red-500 mr-3"></i>
                <h2 class="text-3xl font-bold text-gray-800">代码实现</h2>
            </div>
            <div class="bg-white rounded-xl overflow-hidden shadow-md">
                <div class="bg-gray-800 px-4 py-2 flex items-center">
                    <div class="w-3 h-3 rounded-full bg-red-500 mr-2"></div>
                    <div class="w-3 h-3 rounded-full bg-yellow-500 mr-2"></div>
                    <div class="w-3 h-3 rounded-full bg-green-500 mr-2"></div>
                    <span class="text-gray-300 ml-2 text-sm">intersect.py</span>
                </div>
                <div class="code-block p-6 overflow-x-auto">
                    <pre class="text-gray-300 font-mono text-sm">
<span class="text-purple-400">def</span> <span class="text-yellow-300">intersect</span>(nums1, nums2):
    <span class="text-purple-400">from</span> collections <span class="text-purple-400">import</span> Counter
    <span class="text-gray-500"># 统计第一个数组的元素频率</span>
    counter = <span class="text-blue-400">Counter</span>(nums1)
    result = []
    <span class="text-purple-400">for</span> num <span class="text-purple-400">in</span> nums2:
        <span class="text-purple-400">if</span> counter[num] > <span class="text-green-400">0</span>:
            result.<span class="text-blue-400">append</span>(num)
            counter[num] -= <span class="text-green-400">1</span>
    <span class="text-purple-400">return</span> result</pre>
                </div>
            </div>
        </section>

        <!-- Key Takeaways -->
        <section>
            <div class="flex items-center mb-6">
                <i class="fas fa-key text-2xl text-indigo-500 mr-3"></i>
                <h2 class="text-3xl font-bold text-gray-800">关键要点</h2>
            </div>
            <div class="grid md:grid-cols-3 gap-6">
                <div class="card bg-white rounded-xl p-6">
                    <div class="w-12 h-12 rounded-full bg-indigo-100 flex items-center justify-center mb-4">
                        <i class="fas fa-clock text-indigo-600"></i>
                    </div>
                    <h3 class="text-xl font-bold text-gray-800 mb-2">时间复杂度</h3>
                    <p class="text-gray-700">哈希表方法在大多数情况下更高效，特别是当数组未排序时。</p>
                </div>
                <div class="card bg-white rounded-xl p-6">
                    <div class="w-12 h-12 rounded-full bg-green-100 flex items-center justify-center mb-4">
                        <i class="fas fa-memory text-green-600"></i>
                    </div>
                    <h3 class="text-xl font-bold text-gray-800 mb-2">空间复杂度</h3>
                    <p class="text-gray-700">双指针方法在空间上更优，但前提是允许修改输入数组。</p>
                </div>
                <div class="card bg-white rounded-xl p-6">
                    <div class="w-12 h-12 rounded-full bg-blue-100 flex items-center justify-center mb-4">
                        <i class="fas fa-check-circle text-blue-600"></i>
                    </div>
                    <h3 class="text-xl font-bold text-gray-800 mb-2">选择策略</h3>
                    <p class="text-gray-700">如果数组已排序或可以排序，优先选择双指针方法；否则使用哈希表。</p>
                </div>
            </div>
        </section>
    </main>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: false,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>